package all;

import leetcodeHis.ListNode;
import test0ne.TreeNode;

import java.util.*;

/**
 * @author by zhangleishuidihuzhu.com
 * @Date 2023/2/21 19:24
 */
public class TestII {

    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();

////        ListNode head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);

        TestII t = new TestII();
//        t.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});

//        List<List<Integer>> list = t.combinationSum2(new int[]{2,5,2,1,2}, 5);
//        System.out.println();
        int[][] array= new int[][]{{1,2,3},{4,5,6}};
//        System.out.println(t.minPathSum(array));
//        t.search(new int[]{1,0,1,1,1}, 0);
        System.out.println();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(2);
//        root.right.right = new TreeNode(7);
        System.out.println(t.isSymmetric(root));

    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }

        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (list.size()>0) {
            int size = list.size();
            String s = "";
            for (int i = 0; i < size; i++) {
                TreeNode cur = list.poll();
                if(cur.left!= null) {
                    list.add(cur.left);
                    s += cur.left.val;
                }else {
                    s += "#";
                }
                if(cur.right != null) {
                    list.add(cur.right);
                    s += cur.right.val;
                }else {
                    s += "#";
                }
            }

            int l = 0;
            int r = s.length()-1;
            while (l<r) {
                if(s.charAt(l) != s.charAt(r)) {
                    return false;
                }
                l++;
                r--;
            }
        }
        return true;
    }

    /**
     * 验证二叉搜索树
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        //中序遍历有序

        List<Integer> list = new ArrayList<>();
        inOrder(root, list);

        if(list.size()<=1) {
            return true;
        }else {
            for (int i = 1; i < list.size(); i++) {
                if(list.get(i)<=   list.get(i-1)) {
                    return false;
                }
            }
        }
        return true;
    }

    private void inOrder(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }

    /**
     * 81、搜索旋转数组
     * @param nums
     * @param target
     * @return
     */
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;


        if(nums[left] == nums[right]) {
            while (left<=right) {
                if(nums[left++] == target) {
                    return true;
                }
            }
        }
        while (left<=right) {
            int mid = left + (right-left)/2;

            if(nums[mid] == target) {
                return true;
            }

            if(nums[mid]>=nums[left]) {
                if(nums[left]<=target && target<nums[mid]) {
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }else {
                if(nums[mid]<target && target<=nums[right]) {
                    left = mid+1;
                }else {
                    right = mid-1;
                }
            }
        }
        return false;
    }


    /**
     * 80、删除有序数组中的重复项 II
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len <= 2) {
            return len;
        }
        int index = 0;
        int xie = 0;
        while (len>=0) {
            int count = 1;
            int cur = nums[index++];
            while (cur == nums[index++]) {
                count++;
                if(count <= 2) {
                    xie++;
                }
            }
        }
        return 0;
    }

    /**
     * 78 子集
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        subsetsChild(0, nums, list, result);
        return result;
    }

    private void subsetsChild(int index, int[] nums, LinkedList<Integer> list, List<List<Integer>> result) {
        if(index==nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }

        subsetsChild(index+1, nums, list, result);

        list.add(nums[index]);
        subsetsChild(index+1, nums, list, result);
        list.removeLast();
    }

    /**
     * 77 组合
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        combineChild(1, n, k, list, result);
        return result;
    }

    private void combineChild(int index, int n, int k, LinkedList<Integer> list, List<List<Integer>> result) {
        if(k==0) {
            result.add(new ArrayList<>(list));
            return;
        }
        if(index>n || k<0) {
            return;
        }

        list.add(index);
        combineChild(index+1, n, k-1, list, result);
        list.removeLast();

        combineChild(index+1, n, k, list, result);

    }

    /**
     * 75、颜色分类
     * @param nums
     */
    public void sortColors(int[] nums) {
        int[] arr = new int[3];
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            arr[cur]++;
        }

        int index = 0;
        for (int i = 0; i < 3; i++) {
            int num = arr[i];
            while (num-->=0) {
                nums[index++] = i;
            }
        }
    }


    /**
     * 74、二维数组搜索
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = matrix[i].length-1; j >=0 ; j--) {
                int cur = matrix[i][j];
                if(cur == target) {
                    return true;
                }else if(target>cur) {
                    break;
                }
            }
        }
        return false;
    }

    /**
     * 矩阵置为0
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        Set<Integer> hang = new HashSet<>();
        Set<Integer> lie = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j] == 0) {
                    hang.add(i);
                    lie.add(j);
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if(hang.contains(i) || lie.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }

        return;
    }


    /**
     * 平方根
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if(x<=1) {
            return x;
        }

        int left = 0;
        int right = x;

        while (left<=right) {
            int mid = left + (right-left) /2;

            if(mid*mid == x) {
                return mid;
            }else if(mid == 0) {
                left = mid+1;
            }else if(mid <= x/mid) {
                if((mid+1)>x/(mid+1)) {
                    return mid;
                }
                left = mid+1;
            }else if(mid > x/mid) {
                if((mid-1)<=x/(mid-1)) {
                    return mid-1;
                }
                right = mid-1;
            }
        }
        return left;

    }

    /**
     * 最短路径
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {

        int[][] result = new int[grid.length][grid[0].length];

        result[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; i++) {
            result[i][0] = result[i-1][0] + grid[i][0];
        }
        for (int i = 1; i < grid[0].length; i++) {
            result[0][i] = result[0][i-1] + grid[0][i];
        }

        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                result[i][j] = Math.min(result[i-1][j], result[i][j-1]) + grid[i][j];
            }
        }

        return result[grid.length-1][grid[0].length-1];

    }


    /**
     * 跳跃游戏 II
     * nums = [2,3,1,1,4]
     * 输出: 2
     * 跳到最后一个下标的最小跳跃次数为2
     * @param nums
     * @return
     */
//    public int jump(int[] nums) {
//        int[] arr = new int[nums.length];
//
//    }

    /**
     * 42 接雨水
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int result = 0;

        int index = 0;
        int curMax = height[0];
        for (int i = 1; i < height.length; i++) {
            int cur = height[i];

        }
        return 0;
    }

    /**
     * 63 不同路径2
     * 加了障碍物   arr[][]   1表示有障碍物    0 表示空
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i==0 && j==0 && obstacleGrid[i][j] == 1) {
                    return 0;
                }

                if(obstacleGrid[i][j] == 1) {
                    result[i][j] = 0;
                }else if(obstacleGrid[i][j] == 0){

                    if(i==0 && j > 0) {
                        result[i][j] = result[i][j-1] == 0? 0: 1;
                    }else if(i>0&&j==0) {
                        result[i][j] = result[i-1][j] == 0? 0: 1;
                    }else if(i>0 && j>0){
                        result[i][j] = result[i-1][j] + result[i][j-1];
                    }else if(i==0 && j==0) {
                        return 1;
                    }
                }
            }
        }

//        findPathSum2(m, n, obstacleGrid, result);
        return result[m-1][n-1];
    }

    private int findPathSum2(int m, int n, int[][] obstacleGrid, int[][] result) {
        if(m<0 || n<0) {
            return 0;
        }
        if(obstacleGrid[m][n] == 1) {
            result[m][n] = 0;
            return 0;
        }
        if(m == 0 && n == 0) {
            if(obstacleGrid[0][0] == 1){
                result[m][n] = 0;
            }else {
                result[m][n] = 1;
            }
        }else if(m == 0 && n>0) {
            result[m][n] = findPathSum2(m, n-1, obstacleGrid, result);
        }else if(n == 0 && m>0) {
            result[m][n] = findPathSum2(m-1, n, obstacleGrid, result);
        }
        else {
            int l = result[m-1][n] == 0? findPathSum2(m-1,n,obstacleGrid,result) :result[m-1][n];
            int r = result[m][n-1] == 0? findPathSum2(m,n-1,obstacleGrid,result) :result[m][n-1];
            result[m][n] = l+r;
        }
        return result[m][n];
    }

    /**
     * 62 不同路径
     * 机器人在左上角，往右下角落走，问有多少种路径
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] array = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i==0 || j == 0) {
                    array[i][j] = 1;
                }else {
                    array[i][j] = array[i-1][j] + array[i][j-1];
                }
            }
        }
//        findPathSum(m-1, n-1, array);
        return array[m-1][n-1];
    }

    private int findPathSum(int m, int n, int[][] array) {
        if(m == 0 || n ==0) {
            array[m][n] = 1;
            return 1;
        }
        if(array[m][n] == 0) {
            array[m][n] = findPathSum(m-1, n, array) + findPathSum(m ,n-1, array);
        }
        return array[m][n];
    }


    /**
     * 61 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * @param head
     * @param k
     * 快慢指针找到倒数第k个节点
     * 计算链表长度，如果 k > len 取  k % len
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;

        int len = 0;
        while (cur.next != null) {
            cur = cur.next;
            len++;
        }
        if(k>len) {
            k = k%len;
        }

        ListNode slow = dummy;
        ListNode fast = dummy;
        if(k == 0) {
            return slow.next;
        }
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }

        while (fast.next!= null) {
            slow = slow.next;
            fast = fast.next;
        }

        ListNode result = slow.next;
        slow.next = null;
        fast.next = dummy.next;

        return result;
    }

    /**
     * 56 合并区间
     *
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i+1; j < intervals.length; j++) {
                if(intervals[i][0]> intervals[j][0]) {
                    int[] temp = intervals[i];
                    intervals[i] = intervals[j];
                    intervals[j] = temp;
                }
            }
        }
        if(intervals.length<=1) {
            return intervals;
        }

        int begin = intervals[0][0];
        int end = intervals[0][1];
        List<int[]> list = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];

            if(end< cur[0]) {
                list.add(new int[]{begin, end});
                begin = cur[0];
                end = cur[1];
            }else if(end<cur[1]){
                end = cur[1];
            }
            if(i == intervals.length-1) {
                list.add(new int[]{begin, end});
            }
        }
        int[][] result = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    /**
     * 55 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 判断你是否能够到达最后一个下标。
     * 输入：nums = [2,3,1,1,4]
     * 输出：true
     * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
     * @param candidates
     * @param target
     * 动态规划
     * @return
     */
    public boolean canJump(int[] nums) {
        return canJumpToEnd(nums, 0);
    }

    private boolean canJumpToEnd(int[] nums, int index) {
        if(index == nums.length-1) {
            return true;
        }
        if(index>nums.length-1) {
            return false;
        }
        boolean result = false;
        int cur = nums[index];
        for (int i = cur; i > 0; i--) {
            result = result||canJumpToEnd(nums, index+i);
        }
        return result;
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        Set<List<Integer>> result = new HashSet<>();
        LinkedList<Integer> list = new LinkedList<>();

        findCombinationSumChild(candidates, 0, target, list, result);
        return new ArrayList<>(result);
    }

    private void findCombinationSumChild(int[] candidates, int index, int target, LinkedList<Integer> list, Set<List<Integer>> result) {
        if(target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        if(index>=candidates.length || target < 0) {
            return;
        }

        findCombinationSumChild(candidates, index+1, target, list, result );

        list.add(candidates[index]);
        findCombinationSumChild(candidates, index+1, target-candidates[index], list, result );
        list.removeLast();
    }


    /**
     * 35、搜索被插入的位置
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;

        while (left <= right) {
            int mid = left + (right-left)/2;

            if(nums[mid]==target) {
                return mid;
            }else if(nums[mid]<target) {
                if(mid == nums.length-1 || nums[mid+1] > target) {
                    return mid+1;
                }
                left = mid+1;
            }else if(nums[mid]>target) {
                if(mid == 0) {
                    return 0;
                }
                if(nums[mid-1] < target) {
                    return mid;
                }
                right = mid-1;
            }
        }
        return 0;
    }


    public int firstMissingPositive(int[] nums) {
        int[] array = new int[nums.length+1];

        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0) {
                array[nums[i]] = nums[i];
            }
        }

        for (int i = 1; i < array.length; i++) {
            if(array[i] != i) {
                return i;
            }
        }
        return 0;
    }


    /**
     * 34 排序数组中查找元素的第一个和最后一个位置
     *
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int begin = findLeft(nums, target);
        int end = findRight(nums, target);

        return new int[]{begin, end};
    }

    private int findRight(int[] nums, int target) {
        int result = -1;

        int left = 0;
        int right = nums.length-1;

        while (left<=right) {
            int mid = left + (right -left)/2;
            if(nums[mid] == target) {
                if(mid+1<nums.length ) {
                    if(nums[mid+1] != nums[mid]) {
                        result = mid;
                        break;
                    }else {
                        left = mid+1;
                    }
                }else {
                    result = mid;
                    break;
                }
            }else if(nums[mid] < target) {
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return result;
    }

    private int findLeft(int[] nums, int target) {
        int result = -1;

        int left = 0;
        int right = nums.length-1;

        while (left<=right) {
            int mid = left + (right -left)/2;
            if(nums[mid] == target) {

                if(mid-1>=0 ) {
                    if(nums[mid-1] != nums[mid]) {
                        result = mid;
                        break;
                    }else {
                        right = mid-1;
                    }
                }else {
                    result = mid;
                    break;
                }
            }else if(nums[mid] < target) {
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return result;
    }


    /**
     * 39 组合总数
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Set<List<Integer>> result = new HashSet<>();

        LinkedList<Integer> list = new LinkedList<>();

        findSum(candidates,0, target, list, result);
        return new ArrayList<>(result);
    }

    private void findSum(int[] candidates,int index, int target, LinkedList<Integer> list, Set<List<Integer>> result) {
        if(target<0 || index>=candidates.length) {return;}
        if(target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        //放入
        list.add(candidates[index]);
        findSum(candidates, index, target-candidates[index], list, result);
        list.removeLast();

        list.add(candidates[index]);
        findSum(candidates, index+1, target-candidates[index], list, result);
        list.removeLast();

        //不放
        findSum(candidates, index+1, target, list, result);
    }

    /**
     * 33. 搜索旋转排序数组
     * @param nums
     * @param target
     * @return
     */
//    public int search(int[] nums, int target) {
//        //二分查找， mid == target 找到了，
//
//        int left = 0;
//        int right = nums.length-1;
//
//        while (left<=right) {
//            int mid = left + (right - left ) /2;
//            int cur = nums[mid];
//            if(cur == target) {
//                return mid;
//            }else if(cur > nums[nums.length-1]) {
//                //落在前半段
//                if(cur > target && nums[0]<=target) {
//                    right = mid-1;
//                }else {
//                    left = mid+1;
//                }
//            }else {
//                if(cur < target && target<=nums[nums.length-1]) {
//                    left = mid+1;
//                }else {
//                    right = mid-1;
//                }
//            }
//        }
//        return left;
//    }




    /**
     * 最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if(s.length() <=1) {
            return s;
        }

        int maxLen = 0;
        int begin = 0;

        boolean[][] array = new boolean[s.length()+1][s.length()+1];
        for (int i = 0; i < s.length(); i++) {
            array[i][1] = true;
        }

        for (int len = 2; len <= s.length(); len++) {
            for (int j = 0; j < s.length(); j++) {
                //推出右边界
                int right = j + len -1;
                if(right>s.length()) { break;}

                if(s.charAt(j) != s.charAt(right)) {
                    array[j][right] = false;
                }else {
                    if(right - j<3 || array[j+1][right-1]) {
                        array[j][right] = true;
                    }else {
                        array[j][right] = false;
                    }
                }

                if(array[j][right] && right-j+1>maxLen) {
                    maxLen = right-j+1;
                    begin = j;
                }
            }
        }
        return s.substring(begin, maxLen-1);
    }

    /**
     * 15 三数之和
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            if(i>0 && nums[i] == nums[i-1] ) {
                //表示这个数字作为a，已经记录过
                continue;
            }
            //双指针
            int left = i+1;
            int right = nums.length-1;
            while (left<right) {
                int sum = nums[left]+nums[right]+a;
                if(sum == 0) {
                    result.add(List.of(a, nums[left], nums[right]));

                    while (left<right && nums[left] == nums[left+1]) {
                        left++;
                    }

                    while (left<right && nums[right] == nums[right-1]) {
                        right--;
                    }

                    left++;
                    right--;

                }else if(sum<0) {
                    left++;
                }else {
                    right--;
                }
            }
        }
        return result;
    }

    private List<Integer> twoSum(int target, int[] nums, int left) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> result = new ArrayList<>();

        for (int i = left; i < nums.length; i++) {
            if(map.get(target - nums[i]) != null) {
                result.add(nums[i]);
                result.add(target - nums[i]);
                return result;
            }
            map.put(nums[i], i);
        }
        return result;
    }

    /**
     * 38 每日温度
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> s = new Stack<>();
        int[] result = new int[temperatures.length];
        s.add(temperatures.length-1);
        result[result.length-1] = 0;
        for (int i = temperatures.length - 2; i >= 0; i--) {
            int cur = temperatures[i];
            while (!s.isEmpty() && cur>temperatures[s.peek()]) {
                s.pop();
            }
            if(s.isEmpty()) {
                result[i] = 0;
            }else {
                result[i] = s.peek()-i+1;
            }
            s.add(cur);
        }
        return result;
    }

    /**
     * 37 小行星碰撞
     * @param asteroids
     * @return
     */
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> s = new Stack<>();

        for (int i = 0; i < asteroids.length; i++) {
            int cur = asteroids[i];
            if(s.isEmpty()) {
                s.add(cur);
                continue;
            }
            while (!s.isEmpty()) {
                int peek = s.peek();
                if(peek * cur < 0 && cur<0) {
                    if((cur*-1)>peek) {
                        s.pop();
                        if(s.isEmpty()) {
                            s.add(cur);
                            break;
                        }
                        continue;
                    }else if((cur*-1) == peek){
                        s.pop();
                    }
                    break;
                }
                s.add(cur);
                break;
            }
        }
        int[] result = new int[s.size()];
        int index = result.length-1;
        while (!s.isEmpty()) {
            result[index--] = s.pop();
        }
        return result;
    }

    /**
     * 36 后缀表达式
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> s = new Stack();
        for (int i = 0; i < tokens.length; i++) {
            String cur = tokens[i];
            if(cur.equals("+") ) {
                int b = s.pop();
                int a = s.pop();
                s.add(a+b);
            }else if(cur.equals("-")) {
                int b = s.pop();
                int a = s.pop();
                s.add(a-b);
            }else if(cur.equals("*")) {
                int b = s.pop();
                int a = s.pop();
                s.add(a*b);
            }else if(cur.equals("/")) {
                int b = s.pop();
                int a = s.pop();
                s.add(a/b);
            }else {
                s.add(Integer.parseInt(cur));
            }
        }
        return s.pop();
    }


    /**
     * 35 最小时间差
     * @param timePoints
     * @return
     */
    public int findMinDifference(List<String> timePoints) {
        int[] arr = new int[timePoints.size()];

        int last = 23*60+59;
        for (int i = 0; i < timePoints.size(); i++) {
            String[] str = timePoints.get(i).split(":");
            arr[i] =  Integer.parseInt(str[0]) * 60 + Integer.parseInt(str[1]);
        }
        Arrays.sort(arr);

        int result = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            int cur = arr[i]-arr[i-1];
            if(cur == 0) {
                return 0;
            }
            result = Math.min(result, cur);
        }
        result = Math.min(arr[0]+last - arr[arr.length-1], result);
        return result;
    }

    /**
     * 31 最近最少使用缓存
     */
    public static class LRUCache {

        public Map<Integer, Integer> map;

        public LinkedList<Integer> list;

        public int cap;

        public LRUCache(int capacity) {
            map = new HashMap<>();
            list = new LinkedList<>();
            cap = capacity;
        }

        public int get(int key) {
            if(map.get(key)!=null) {
                addFirst(key);
            }
            return map.getOrDefault(key,-1);
        }

        private void addFirst(int key) {
            int index = 0;
            for (int i = 0; i < list.size(); i++) {
                if(list.get(i) == key) {
                    index = i;
                    break;
                }
            }
            list.remove(index);
            list.addFirst(key);
        }

        public void put(int key, int value) {
            if(map.get(key)!=null) {
                addFirst(key);
                map.put(key, value);
            }else {
                if(map.size() == cap) {
                    int last = list.getLast();
                    list.removeLast();
                    map.remove(last);
                }
                list.addFirst(key);
                map.put(key, value);
            }
        }
    }

    /**
     * 44 二叉树每层的最大值
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }
        LinkedList<TreeNode> list = new LinkedList<>();

        List<Integer> result = new ArrayList<>();
        list.add(root);
        while (list.size()>0) {
            int sum = list.size();
            int cur = Integer.MIN_VALUE;
            for (int i = 0; i < sum; i++) {
                TreeNode r = list.poll();
                if(r.left != null) {
                    list.add(r.left);
                }
                if(r.right != null) {
                    list.add(r.right);
                }
                cur = Math.max(cur, r.val);
            }

            result.add(cur);
        }
        return result;
    }

    /**
     * 27 回文链表
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) {
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next !=null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode last = reverseList(slow.next);
//        if(fast.next == null) {
//            //奇数
//        }
        ListNode a = head;
        ListNode b = last;
        while (b!=null) {
            if(a.val != b.val) {
                return false;
            }
            b = b.next;
            a = a.next;
        }
        return true;
    }

    /**
     * 26 重排链表
     * @param head
     */
    public void reorderList(ListNode head) {
        //1、找到中间节点   fast.next = null 奇数 此时 slow走到中点   fast.next.next = null 偶数，此时slow走到前半部分最后一个
        //2、反转后面半部分
        //3、重新生成链表
        if(head==null || head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next !=null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode last = reverseList(slow.next);
        slow.next = null;
        ListNode a = head;
        ListNode b = last;
        while (b!=null) {
            ListNode aNext = a.next;
            ListNode bNext = b.next;
            a.next = b;
            b.next = aNext;
            a = aNext;
            b = bNext;
        }
    }

    /**
     * 25、链表中的两数相加
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l1R = reverseList(l1);
        ListNode l2R = reverseList(l2);

        ListNode result = new ListNode(-1);
        ListNode cur = result;
        int sum = 0;
        while (l1R != null || l2R != null) {
            int a = l1R == null? 0:l1R.val;
            int b = l2R == null? 0:l2R.val;
            int n = a + b + sum;
            cur.next = new ListNode(n%10);
            cur = cur.next;
            sum = n/10;

            if(l1R != null) {
                l1R = l1R.next;
            }
            if(l2R != null) {
                l2R = l2R.next;
            }
        }

        if(sum>0) {
            cur.next = new ListNode(1);
            cur = cur.next;
        }

        return reverseList(result.next);
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 23 两个链表的第一个重合节点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int alen = 0;
        int blen = 0;

        ListNode a = headA;
        ListNode b = headB;
        while (a!=null && a.next!=null) {
            a = a.next;
            alen++;
        }
        while (b!=null && b.next!=null) {
            b = b.next;
            blen++;
        }

        if(a != b) {return null;}

        if(alen==blen) {
            return headA;
        }else if(alen>blen) {
            a = headA;
            b = headB;
            int gap = alen-blen;
            for (int i = 0; i < gap; i++) {
                a = a.next;
            }
            while (a!=b) {
                a = a.next;
                b = b.next;
            }
            return a;
        }else if(alen<blen) {
            a = headA;
            b = headB;
            int gap = blen-alen;
            for (int i = 0; i < gap; i++) {
                b = b.next;
            }
            while (a!=b) {
                a = a.next;
                b = b.next;
            }
            return a;
        }
        return null;
    }

    /**
     * 22 链表中环的入口节点
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        //1、先检测环
        //2、找环的入口节点

        if(head == null || head.next==null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;

        while (slow != fast) {
            if(fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode start = head;
        while (start != slow) {
            start = start.next;
            slow = slow.next;
        }


        return start;
    }

    /**
     * 删除链表倒数第n个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        while (fast!= null) {
            slow = slow.next;
            fast = fast.next;
        }

        if(slow.next.next == null) {
            slow.next = null;
        }else {
            slow.next = slow.next.next;
        }
        return dummy.next;
    }

    /**
     * 20 回文字符串的个数
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(isPalindrome3(s,i,j)) {
                    result++;
                }
            }
        }
        return result;
    }

    private boolean isPalindrome3(String s, int left, int right) {
        while (left<=right) {
            if(s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 19 最多删除一个字符得到回文
     * @param s
     * @return
     */
    public boolean validPalindrome(String s) {
        if(s.length()<=1) {return true;}

        return validPalindrome2(s, 0, s.length()-1);
    }

    private boolean validPalindrome2(String s, int left, int right) {
        return validPalindrome3(s, left+1, right) || validPalindrome2(s, left, right-1);
    }

    private boolean validPalindrome3(String s, int left, int right) {

        boolean flag = false;
        while (left<=right) {

            if(s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            }else if(!flag && s.charAt(left+1) == s.charAt(right)) {
                left++;
                flag = true;
            }else if(!flag && s.charAt(left) == s.charAt(right--)) {
                right--;
                flag =true;
            }else {
                return false;
            }
        }
        return true;
    }

    public boolean isPalindrome2(String s) {
        if(s.length()<=1) {return true;}

        int left = 0;
        int right = s.length()-1;
        while (left<=right) {
            String a = s.charAt(left++)+"";
            String b = s.charAt(right--)+"";
            if(!a.equalsIgnoreCase(b)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 18 验证有效回文
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        if(s.length()<=1) {return true;}

        int left = 0;
        int right = s.length()-1;
        while (left<=right) {
            while (left<s.length() && !Character.isDigit(s.charAt(left)) && !Character.isAlphabetic(s.charAt(left))) {
                left++;
            }
            while (right>=0 && !Character.isDigit(s.charAt(right)) && !Character.isAlphabetic(s.charAt(right))) {
                right--;
            }
            if(left>right) {
                return false;
            }
            String a = s.charAt(left++)+"";
            String b = s.charAt(right--)+"";
            if(!a.equalsIgnoreCase(b)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 209 和大于等于 target 的最短子数组
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int length = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int sum = nums[left];
        while (left<=right && right<nums.length-1) {
            while (sum<target) {
                right++;
                sum+=nums[right];
            }
            while (sum>=target) {
                length = Math.min(length, right-left+1);
                sum -= nums[left++];
            }

        }
        return length;
    }


    /**
     * 专项 9
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            int result = 1;
            for (int len = 1; len <= nums.length-i; len++) {
                result *= nums[i+len-1];
                if(result<k) {
                    num++;
                }else {
                    break;
                }
            }
        }
        return num;
    }
    public int numSubarrayProductLessThanK2(int[] nums, int k) {
        int count = 0;
        int product = 1;
        int left = 0, right = 0;
        for (;right < nums.length; right++) {
            product *= nums[right];
            while (left<=right && product>=k) {
                product/= nums[left++];
            }
            count += right>=left? right-left+1 :0;
        }
        return count;
    }

    /**
     * 16 不含重复字符的最长字符串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        //1、哈希表记录存在的字符
        //2、index记录移动的下标

        Map<Character, Integer> map = new HashMap<>();
        int index = 0;
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if(map.get(cur) == null) {
                map.put(cur, i);
            }else {
                int l = map.get(cur);
                while (index<=l) {
                    map.remove(s.charAt(index++));
                }
                map.put(cur,i);
            }
            result = Math.max(result, map.size());
        }
        return  result;
    }
}
